// General.cs
// 
// This class is a place holder for methods which have yet to placed into
// a more suitable class file

using System;
using System.Collections.Generic;
using System.Linq;

namespace Mono.Algorithm
{
	public partial class Algorithm
	{
		public static Dictionary<int, int> Greedy(List<int> candidates, int value)
		{
			Dictionary<int, int> results = new Dictionary<int, int>();
			candidates = Sort<int>(candidates, 0, candidates.Count - 1, SortOrder.Descending);
			
			GreedyGetNextValue(ref candidates, ref results, ref value);
			
			return results;
		}
		
		private static void GreedyGetNextValue(ref List<int> candidates, ref Dictionary<int, int> results, ref int value)
		{
			bool resultFound = false; 
			
			foreach (int candidate in candidates)
			{
				if (candidate <= value)
				{
					if (results.ContainsKey(candidate))
					{
						results[candidate]++;
					}
					else
					{
						results.Add(candidate, 1);
					}
					
					value -= candidate;
					resultFound = true;
					break;
				}
			}
			
			if (false == resultFound)
			{
				return;
			}
			else if (value > 0)
			{
				GreedyGetNextValue(ref candidates, ref results, ref value);
			}
		}
	}
}
